import java.util.Arrays;

public class TestHeap {
    public int[] elem;
    public int usedSize;


    public TestHeap(){
        this.elem=new int[11];
    }

    public void init(int[] array) {
        for (int i = 0; i<array.length;i++){
            elem[i] = array[i];
            usedSize++;
        }
    }

       //把elem数组当中的数据 调整为大根堆
        public void createHeap(){
        for (int parent=(usedSize-1-1)/ 2;parent>=0;parent--){
             siftDown(parent,usedSize);
            }
        }


         private   void swap(int i,int j){
         int tmp=elem[i];
         elem[i]=elem[j];
         elem[j]=tmp;
       }


        public void siftDown(int parent,int end){
        int child=2*parent+1;
        while (child<end){
            if (elem[child]<elem[child+1]){
                child++;
            }
            //child下标 就是 左右孩子的最大值
            if(elem[child] >elem[parent]){
            swap(child,parent);
            parent=child;
            child=2*parent+1;
            }else {
                break;
            }

        }
    }

    public void offer(int val){
    if (isFull()){
       elem= Arrays.copyOf(elem,2*elem.length);
    }
    elem[usedSize]=val;
    usedSize++;
    siftUp(usedSize-1);
    }

    public void siftUp(int child){
        int parent=(child-1)/2;
        while (parent>=0){
      if(elem[child]>elem[parent]){
        swap(child,parent);
        child=parent;
        parent=(child-1)/2;
      }else{
          break;
      }
        }
    }
    public boolean isFull(){
        return usedSize==elem.length;
    }
    public int poll() {
        if (isEmpty()) {
            return -1;
        }
        int old=elem[0];
        swap(0,usedSize-1);
        siftDown(0,usedSize);
    }
    public boolean isEmpty(){
        return usedSize==0;
    }
}

